package work.xiaohong.arithmetic.SortArithmetic;

/**
 * @author xiaohong
 * @version 1.0
 * @date 2021/10/28 0028 10:42
 * @description 归并排序
 * 时间复杂度 O（nlogn）
 */
public class Merge {

    /**
     * 排序原理
     * 1.尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止。
     * ⒉.将相邻的两个子组进行合并成一个有序的大组;
     * 3.不断的重复步骤2，直到最终只有一个组为止。
     *
     * 稳定的排序算法
     */
    
    // 归并需要的辅组数组
    private static Comparable[] assist;
    
    public static void mergeSort(Comparable[] a){
        // 初始化辅组数组assist
        assist = new Comparable[a.length];
        
        // 定义lo,hi变量，分别记录数组中最小的索引和最大的索引
        int lo = 0;
        int hi = a.length-1;
        
        // 调用sort重载方法完成数组a中，从索引lo到hi的元素排序
        sort(a,lo,hi);
        
    }

    /**
     * 对数组a从索引lo到hi的元素排序
     * @param a
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] a, int lo, int hi) {
        // 做安全校验
        if (hi <= lo){
            return;
        }

        // 对lo和hi之间的数据分成两个组
        int mid = lo+(hi-lo)/2;

        // 分别对每一组数据进行排序
        sort(a,lo,mid);
        sort(a,mid+1,hi);

        // 把两个组中的数据进行归并
        merge(a,lo,mid,hi);

    }

    /**
     * lo到mid为一组，mid+1到hi为一组，对这两组数据进行归并
     * @param a
     * @param lo
     * @param mid
     * @param hi
     */
    private static void merge(Comparable[] a, int lo, int mid, int hi) {
        // 定义三个指针
        int i = lo;
        int p1 = lo;
        int p2 = mid+1;

        // 遍历，移动p1和p2指针，比较对应索引处的值，找出小的哪个，放到赋值数组的对应索引处
        while (p1 <= mid && p2 <= hi){
            if (!SortUtils.greater(a[p1],a[p2])){
                assist[i++] = a[p1++];
            }else {
                assist[i++] = a[p2++];
            }
        }

        // 遍历，如果p1指针没有走完，那么顺序移动p1指针，把对应的元素放到辅组数组的对应索引处
        while (p1 <= mid){
            assist[i++] = a[p1++];
        }

        // 遍历，如果p2指针没有走完，那么顺序移动p2指针，把对应的元素放到辅组数组的对应索引处
        while (p2 <= hi){
            assist[i++] = a[p2++];
        }

        // 把辅组数组的元素拷贝到原数组中
        for (int index = lo; index <= hi; index++){
            a[index] = assist[index];
        }

    }


}